import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 895. 最大频率栈
 * https://leetcode-cn.com/problems/maximum-frequency-stack/
 */
public class Solutions_895 {
    public static void main(String[] args) {
        FreqStack obj = new FreqStack();
        obj.push(5);
        obj.push(7);
        obj.push(5);
        obj.push(7);
        obj.push(4);
        obj.push(5);
        int res1 = obj.pop();  // output: 5
        int res2 = obj.pop();  // output: 7
        int res3 = obj.pop();  // output: 5
        int res4 = obj.pop();  // output: 4
    }
}

/**
 * 解题思路：栈实现
 * 例：当 5，7，5，7，4，5 元素入栈后
 * 此时 group 存储的是：
 * 1 -> 5，7，4  （4 是栈顶）
 * 2 -> 5，7  （7 是栈顶）
 * 3 -> 5
 * 再根据 maxfreq，那么依次从 group 中 pop 的元素就是 5，7，5，4，7，5
 */
class FreqStack {
    // key：元素，value：出现的次数
    Map<Integer, Integer> freq = null;
    // key：出现次数，value：记录出现 key 次的元素
    Map<Integer, Stack<Integer>> group;
    // 记录最大频率
    int maxfreq = 0;

    public FreqStack() {
        freq = new HashMap<>();
        group = new HashMap<>();
        maxfreq = 0;
    }

    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        if (f > maxfreq) {
            // 记录最大频率
            maxfreq = f;
        }
        if (!group.containsKey(f)) {
            group.put(f, new Stack<>());
        }
        group.get(f).push(x);
    }

    public int pop() {
        int stackTop = group.get(maxfreq).pop();
        // 栈顶元素出现次数减 1
        freq.put(stackTop, freq.get(stackTop) - 1);
        if (group.get(maxfreq).size() == 0) {
            // 最大频率减 1
            maxfreq --;
        }
        return stackTop;
    }
}
